Exercises with invariants

For these exercises, remember that your purpose statement, including its invariant, is at least as important as your function definition.

When you are called on, please copy your solution into one of the following pages:

• bitly.com/cs5010f14-solutions-1
• bitly.com/cs5010f14-solutions-2

1. Consider the following constructor template for binary trees:

   A Bintree is one of
   -- (leaf-node Number)
   -- (tree-node Number Bintree Bintree)
     

   Design a function called tree-with-leaf-sums which, given a Bintree, returns a Bintree of the same shape, but in which each leaf node is replaced by the sum of all the numbers on the path from the root to the leaf.

   Example:
   #(struct:tree-node 3
      #(struct:tree-node 4
         #(struct:leaf-node 5)
         #(struct:leaf-node 10))
      #(struct:leaf-node 2))
   
   =>
   
   #(struct:tree-node 3
      #(struct:tree-node 4
         #(struct:leaf-node 12)   ; 3 + 4 + 5 = 12
         #(struct:leaf-node 17))  ; 3 + 4 + 10 = 17
      #(struct:leaf-node 5))      ; 3 + 2 = 5
   

2. Do the same thing, except the data is defined by:

   A Bintree is one of
   -- Number
   -- (list Number Bintree Bintree)
   

   Here we are using a list in place of a struct, like we do in ps06. In this representation, the tree in the example above would be represented (in write output mode) by:

   (3
     (4 12 17)
     5)
   

3. Do the same thing, except for the data type defined by the constructor template

   A Tree is a
   -- (make-tree Number ListOfTree)   
   
   A ListOfTree is one of
   -- empty
   -- (cons Tree ListOfTree)
   

   For these trees, we define a leaf to be a tree with an empty list of daughters.
4. You are writing code for a navigation program. You are to write a function called distances-so-far which, given a list of point-to-point distances, produces a list of distances to be displayed as "distance travelled so far"

   EXAMPLE: Say there are 4 points on the route, called A, B, C, and D.
   D is the destination.  The distance from A to B is 10, from B to C is
   2, and from C to D is 5.  For this route, the input to your function
   is the list
   (10 2 5)
   and your function should return the list
   (0 10 12 17)